1. Field of the Invention
The present invention relates to communications applications that require the sequence of data bits transmitted over a communication channel to be statistically random. The ISDN Interface is one example of such an application, since proper training and operation of its associated echo canceller requires both a statistically random sequence of bits, and statistical independence (orthogonality) of the transmit and receive data in the two directions of transmission. In order to achieve the required degree of randomness, the data can be "scranbled" using a Maximal Length Pseudo Random sequence. Maximal Length Pseudo Random Sequences are known to have the lowest possible auto-correlation, and are therefore the optimal choice for scrambling.
The present invention is thus useful in digital communication systems where bits must be "scrambled" in order to obtain a statistically random distribution of bits even though the actual input and output bits may be far from random. For exmaple, the input bits at the transmit end of a communication path may be all "zeros", all "ones", or repetitive patterns; however, for best use of the transmission channel the bits actually transmitted must be randomly or pseudo-randomly distributed. At the receive end of the transmission path, the output bits must be restored to their proper values.
2. Description of the Prior Art
Two techniques have been generally used in the prior art to perform the scrambling operation: block scrambling and stream scrambling. Both techniques take advantage of the fact that when a first sequence of bits is exclusive Or'ed with a second sequence of bits and is then again exclusive Or'ed with the second sequence of bits identically aligned, the output is the first sequence just as it was before any exclusive OR operations were performed.
Block scrambling uses a framing pattern or other known means to divide the bits into some definable blocks of information. These bits are then exclusive Or'ed with a fixed pattern of bits synchronized to the boundaries of the block. Since the pattern of scrambling bits is fixed with respect to the block, the same pattern can be used at the receiver end to un-scramble the bits. Any bit error occurring in the transmission channel between the transmitter and receiver will cause an error in that particular bit, but will not cause other bits to be in error, provided only that the receiver remains synchronized with the transmitter as to the block boundaries.
Block scrambling has the disadvantage that the longest framing pattern in a typical communication system is usually shorter than the length of the scrambling pattern needed to assure sufficient "randomness" in the transmitted bits. In addition, the longest framing pattern is not usually equal to the 2.sup.N -1 length of the Pseudo-Random pattern desired, so that only part of the pattern is used repetitively, introducing undesirable correlations in the data.
Stream scrambling of the known prior art generally operates on a continuous stream of bits. In a typical implementation the bits at the transmit end of a communication channel to be scrambled are passed through one input of a two input exclusive Or gate. The output of the gate is the output of the scrambler and also the input to an "N" stage shift register. This shift register is tapped at the N.sup.th stage and one or more other stages, and the outputs of these taps are exclusive Or'ed together. The result of this exclusive Or operation is applied to the other input of the exclusive Or gate that has the data to be scrambled, as the first input. The tap positions are chosen so that a Galois polynomial represented by the tap weights is irreducible, and if the input data were all zeros and the shift register started out at any state other than all zeros, a Maximal Length Pseudo-Random Shift Register Sequence would be produced.
Stream scrambling of the prior art has the disadvantage that it multiplies transmission errors. When a transmission error occurs, an immediate error is output from the receiver because the input bit was wrong. This wrong bit is also applied to the input of the receive shift register and causes an additional error each time it passes a tap on the register, a minimum of two taps for a Pseudo-Random register. This at least triples the number of bit errors and, when the bit stream consists of several channels multiplexed together, can introduce errors onto channels which would have been error-free but for the error multiplying effect of the scrambler.
At the receiver end the received "scrambled" bits are passed directly into a shift register identical to the shift register at the transmit end. The scrambled bits are also applied to one input of an exclusive Or gate. The receive shift register is tapped identically to the shift register at the transmit end and the taps are exclusive Or'ed together, with the output of the exclusive Or gate of the taps being applied to the second input of the exclusive Or gate which has its first input connected to the received "scrambled" bits.
It is apparent that in the absence of transmission errors, the input to the shift registers at the transmit and receive ends is identical: it is the scrambled data bits. After "N" bits have been transmitted, the contents of the receive shift register are identical with the contents of the transmit shift register and the bits fed back from the taps are the same. Thus the received scrambled data is again exclusive Or'ed with the same pattern of bits from the shift register and is restored to its original "unscrambled" form.